package leetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * ClassName: DataStructureOfString
 * Package: leetcode
 * Description:
 *
 * @Author wjn
 * @Create 2025/5/29 15:02
 * @Version 1.0
 */
public class DataStructureOfString {

    /**
     * 交换数组中两个元素
     */
    public void swap(char[] nums, int i, int j) {
        nums[i] = (char) (nums[i] ^ nums[j]);
        nums[j] = (char) (nums[i] ^ nums[j]);
        nums[i] = (char) (nums[i] ^ nums[j]);
    }


    /**
     * 反转字符串
     * 收尾交换（双指针）
     *
     * @param s
     */
    public void reverseString(char[] s) {
        int len = s.length;
        for (int i = 0, j = len - 1; i < len / 2; j--, i++) {
            s[i] ^= s[j];
            s[j] ^= s[i];
            s[i] ^= s[j];
        }
    }

    public void reverseString2(char[] s, int left, int right) {
        while (left < right) {
            s[left] ^= s[right];
            s[right] ^= s[left];
            s[left] ^= s[right];
            left++;
            right--;
        }
    }

    public String reverseStr(String s, int k) {
        int len = s.length();
        char[] chars = s.toCharArray();
        for (int i = 0; i < len; i += 2 * k) {
            reverseString2(chars, i, Math.min(i + k, len) - 1);
        }
        return new String(chars);
    }

    /**
     * 反转单词
     * 移除多余空格
     * 将整个字符串反转
     * 将每个单词反转
     *
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        // System.out.println("ReverseWords.reverseWords2() called with: s = [" + s + "]");
        // 1.去除首尾以及中间多余空格
        StringBuilder sb = removeSpace(s);
        // 2.反转整个字符串
        reverseString(sb, 0, sb.length() - 1);
        // 3.反转各个单词
        reverseEachWord(sb);
        return sb.toString();
    }

    private void reverseEachWord(StringBuilder sb) {
        int start = 0;
        int end = 1;
        int n = sb.length();
        while (start < n) {
            while (end < n && sb.charAt(end) != ' ') {
                end++;
            }
            reverseString(sb, start, end - 1);
            start = end + 1;
            end = start + 1;
        }
    }

    private void reverseString(StringBuilder sb, int start, int end) {
        while (start < end) {
            char temp = sb.charAt(start);
            sb.setCharAt(start, sb.charAt(end));
            sb.setCharAt(end, temp);
            start++;
            end--;
        }
    }

    private StringBuilder removeSpace(String s) {
        // System.out.println("ReverseWords.removeSpace() called with: s = [" + s + "]");
        int start = 0;
        int end = s.length() - 1;
        while (s.charAt(start) == ' ') start++;
        while (s.charAt(end) == ' ') end--;
        StringBuilder sb = new StringBuilder();
        while (start <= end) {
            char c = s.charAt(start);
            if (c != ' ' || sb.charAt(sb.length() - 1) != ' ') {
                sb.append(c);
            }
            start++;
        }
        // System.out.println("ReverseWords.removeSpace returned: sb = [" + sb + "]");
        return sb;
    }

    public String reverseWordslk(String s) {
        // 除去开头和末尾的空白字符
        s = s.trim();
        // 正则匹配连续的空白字符作为分隔符分割
        List<String> wordList = Arrays.asList(s.split("\\s+"));
        Collections.reverse(wordList);
        return String.join(" ", wordList);
    }

    /**
     * 实现 strStr()
     *
     * @param haystack
     * @param needle
     * @return
     */
    public int strStr(String haystack, String needle) {

        return 0;
    }

    /**
     * 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
     *  解法1 （移动匹配）
     * @param s
     * @return
     */
    public boolean repeatedSubstringPattern(String s) {

        String ss = s + s;
        // 截取首尾字符
        ss = ss.substring(1, ss.length() - 1);
        //  判断是否包含
        return ss.contains(s);

    }


}
